The present invention relates to adaptive filters, and in particular, to fast affine projection (FAP) adaptive filters providing a stability of operation, and methods of stable FAP adaptive filtering.
Adaptive filtering is a digital signal processing technique that has been widely used in technical areas such as, e.g., echo cancellation, noise cancellation, channel equalization, system identification and in products like, e.g., network echo cancellers, acoustic echo cancellers for full-duplex handsfree telephones and audio conference systems, active noise control, data communications systems.
The characteristics of an adaptive filter are determined by its adaptation algorithm. The choice of the adaptation algorithm in a specific adaptive filtering system directly affects the performance of the system.
Being simple and easily stable, the normalized least mean square (NLMS) adaptation algorithm, being a practical implementation of the least mean square (LMS) algorithm, is now most widely used in the industry with a certain degree of success.
However, because of its intrinsic weakness, the NLMS algorithm converges slowly with colored training signals like the speech, an important class of signals most frequently encountered in many applications such as telecommunications. The performance of systems incorporating NLMS adaptive filters very often suffers from the slow convergence nature of the algorithm. Other known algorithms proposed so far are either too complicated to implement on a commercially available low-cost digital signal processor (DSP) or suffer from numerical problems. Recently, a fast affine projection (FAP) method was proposed as described in a publication by Steven L. Gay and Sanjeev Tavathia (Acoustic Research Department, ATandT Bell Laboratories), xe2x80x9cThe Fast Affine Projection Algorithm,xe2x80x9d pp. 3023-3026, Proceedings of the International Conference on Acoustics, Speech, and Signal Processing, May 1995, Detroit, Mich., U.S.A. The FAP is a simplified version of the more complicated, and therefore less practical, affine projection (AP) algorithm. With colored train signals such as the speech, the FAP usually converges several times faster than the NLMS, with only a marginal increase in implementation complexity.
However, a stability issue has been preventing FAP from being used in the industry. A prior art FAP implementation oscillates within a short period of time even with floating-point calculations. This results from the accumulation of finite precision numerical errors in a matrix inversion process associated with the FAP. Researchers have been trying to solve this problem, but no satisfactory answer has been found so far. A remedy proposed in the publication listed above and reinforced in publication by Q. G. Liu, B. Champagne, and K. C. Ho (Bell-Northern Research and INRS-Txc3xa9lxc3xa9communications, Universitxc3xa9 du Quxc3xa9bec), xe2x80x9cOn the Use of a Modified Fast Affine Projection Algorithm in Subbands for Acoustic Echo Cancellation,xe2x80x9d pp. 354-357, Proceedings of 1996 IEEE Digital Signal Processing Workshop, Loen, Norway, September 1996, is to periodically re-start a new inversion process in parallel with the old one, and to use it to replace the latter so as to get rid of the accumulated numerical errors therein. While this can be a feasible solution for high-precision DSPs such as a floating-point processor, it is still not suitable for fixed-point DSP implementations because then the finite precision numerical errors would accumulate so fast that the re-starting period would have to be made impractically small, not to mention the extra complexity associated with this part of the algorithm.
Therefore there is a need in the industry for development of alternative adaptive filtering methods which would ensure stability of operation while providing fast convergence and reliable results.
It is an object of the present invention to provide an adaptive filter and a method of adaptive filtering which would avoid the afore-mentioned problems.
According to one aspect of the present invention there is provided a method of adaptive filtering, comprising the steps of:
(a) determining adaptive filter coefficients;
(b) defining a normalized step size;
(c) updating the filter coefficients, comprising:
determining auto-correlation matrix coefficients from a reference input signal, and
solving at least one system of linear equations whose coefficients are the auto-correlation matrix coefficients, the system being solved by using a descending iterative method having an inherent stability of its operation, the results of the solution being used for updating the filter coefficients and the number of systems of linear equations to be solved being dependent on the normalized step size;
(d) repeating the steps (b) and (c) required number of times.
Advantageously, determining of the auto-correlation matrix is performed recursively. The normalized step size may be chosen to be equal to any value from 0 to 1 depending on the application. In the majority of applications, it is often set to be close to unity or equal to unity. Conveniently, the normalized step size is within a range from about 0.9 to 1.0. Another convenient possibility is to set the normalized step size within a range from about 0.7 to 1.0. For the normalized step size close to unity, the step of solving at least one system of linear equations comprises solving one system of linear equations only. Alternatively, in some applications, e.g., when one needs to keep misadjustment low after convergence, it is required to set the normalized step size substantially less than unity, e.g. less than about 0.7. In this situation the step of solving at least one system of linear equations comprises solving N systems of linear equations, with N being a projection order.
In the embodiments of the invention, a problem of finding the inverse of an auto-correlation matrix which is inherent for other known methods, is reduced to a problem of solving a system of linear equations based on the auto-correlation matrix. The system is solved by one of descending iterative methods which provide inherent stability of operation due to an intrinsic feedback adjustment. As a result inevitable numerical errors are not accumulated. In first and second embodiments of the invention, a steepest descent and conjugate gradient methods are used respectively to determine the first column of the inverse auto-correlation matrix, taking into account that the normalized step size is close to unity. In a third embodiment of the invention a steepest descent or conjugate gradient method is used to determine coefficients of the inverse auto-correlation matrix by recursively solving N systems of linear equations having decrementing orders. It corresponds to the case of the normalized step size being not close to unity. The forth embodiment of the invention avoids determining the inverse of the auto-correlation matrix. Instead, a system of linear equations is solved by using a conjugate gradient method resulting in a solution that can be used directly to determine an updating part of the filter coefficients. Alternatively, other known descending methods, e.g. steepest descent, Newton""s method, PARTAN, quasi-Newton""s method or other known iterative descending methods may also be used. Conveniently, the steps of the method may be performed by operating with real value or complex value numbers.
The method described above is suitable for a variety of applications, e.g. echo cancellation, noise cancellation, channel equalization, system identification which are widely used in products such as network echo cancellers, acoustic echo cancellers for full-duplex handsfree telephones and audio conference systems, active noise control systems, data communication systems.
According to another aspect of the invention there is provided an adaptive filter, comprising:
a filter characterized by adaptive filter coefficients;
means for updating the filter coefficients, including means for setting a normalized step size, the updating means comprising:
a correlator for determining auto-correlation matrix coefficients from a reference input signal, and
a calculator for solving at least one system of linear equations whose coefficients are the auto-correlation matrix coefficients, the system being solved by using a descending iterative method having an inherent stability of its operation, the results of the solution being used for updating the filter coefficients and the number of systems of linear equations to be solved being dependent on the normalized step size.
Advantageously, the calculator is an iterative calculator. Preferably, the calculator is a steepest descent or a conjugate gradient calculator. Alternatively, it may be a calculator performing a Newton""s or quasi-Newton""s method, a PARTAN calculator, or another known iterative descending calculator providing an inherent stability of operation.
Conveniently, the filter and the updating means are capable of operating with real numbers. Alternatively, they may be capable of operating with complex numbers.
The normalized step size may be chosen to be equal to any value from 0 to 1 depending on the application. In the majority of applications, the adaptive filter is often set with the normalized step size close to unity or equal to unity. Conveniently, the normalized step size is within a range from about 0.9 to 1.0. Another convenient possibility is to set the normalized step size within a range from about 0.7 to 1.0. For the normalized step size close to unity, the calculator provides iterative solution of one system of linear equations only at each time interval. Alternatively, in some applications, e.g., when one needs to keep misadjustment after convergence low, it is required to set the normalized step size substantially less than unity, e.g. less than about 0.7. In this situation the calculator provides solutions of N systems of linear equations, with N being a projection order. Conveniently, due to the symmetry of the auto-correlation matrix, determining of the inverse auto-correlation matrix may be performed by solving N systems of linear equations having decrementing orders.
The adaptive filter as described above may be used for echo cancellation, noise cancellation, channel equalization, system identification or other applications where adaptive filtering is required.
The adaptive filter and method described above have an advantage over known FAP adaptive filters by providing a stability of operation. The problem caused by error accumulation in matrix inversion process existing in known FAP filters is solved in the present invention by using iterative descending methods. First, the matrix inversion operation is reduced to a solution of a corresponding system of linear equations based on the auto-correlation matrix. Second, the iterative descending methods, used for the solution of the above system, provide an inherent stability of operation due to an intrinsic feedback adjustment. As a result, inevitable numerical errors are not accumulated, thus providing stability of adaptive filtering.